package com.wkh.datastructure;

import java.util.Iterator;
import java.util.function.Consumer;

//环形链表
public class ToroidalDoublyLinkedSentinelList<E> implements Iterable<Object>{
    private Node sentinel = new Node(null,-1000000,null);

    public ToroidalDoublyLinkedSentinelList() {
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    //头插
    public void addFirst(E value){
        Node last = sentinel.next;
        Node prev = sentinel;//也就是哨兵结点
        Node newNode = new Node(last, value, prev);//新结点
        prev.next = newNode;
        last.prev = newNode;
    }
    //尾插
    public void addLast(E value){
        Node a = sentinel;
        Node b = sentinel.prev;
        Node newNode = new Node(a, value, b);//新结点
        b.next = newNode;
        a.prev = newNode;
    }
    //头删
    public void removeFirst(){
        Node removed = sentinel.next;
        if (removed == sentinel){
            illegalIndexException();
        }
        Node a = sentinel;
        Node b = removed.next;
        a.next = b;
        b.prev = a;

    }
    //尾删
    public void removeLast(){
        Node removed = sentinel.prev;
        if (removed == sentinel){
            illegalIndexException();
        }
        Node a = removed.prev;
        Node b = sentinel;
        a.next = b;
        b.prev = a;
    }

    //递归遍历
    public void loop(Consumer<E> before,Consumer<E> after){
        recursion(sentinel.next,before,after);
    }
    //递归函数
    private void recursion(Node cur, Consumer<E> before, Consumer<E> after) {
        if (cur == sentinel){
            return;
        }
        before.accept((E) cur.value);
        recursion(cur.next, before, after);
        after.accept((E) cur.value);
    }

    private void illegalIndexException() {
        throw new IllegalArgumentException("index不合法");
    }
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    @Override
    public Iterator<Object> iterator() {

        return new Iterator<Object>() {
            Node p = sentinel.next;
            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            //获取返回值并指向下一个结点
            public Object next() {
                Object value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    private static class Node{
        private Node next;
        private Object value;
        private Node prev;

        public Node(Node next, Object value, Node prev) {
            this.next = next;
            this.value = value;
            this.prev = prev;
        }
    }
}
